package LeetCode._01_树;

public class _450_删除二叉搜索树中的节点 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public TreeNode deleteNode(TreeNode root, int key) {
        if(root == null) return null;
        if(root.val == key){ //找到了
            //包括了删除叶子和度位1的节点的情况，返回null或者不为空的节点
            if(root.left == null) return root.right;
            if(root.right == null) return root.left;

            //删除度位2的节点
            TreeNode pre = getPre(root.left); //拿到前驱节点
            root.left = deleteNode(root.left, pre.val); //删除前驱节点
            //前驱节点指向要删除的节点
            pre.left = root.left;
            pre.right = root.right;
            root = pre; //删除
        }else if(root.val > key){
            root.left = deleteNode(root.left,key);
        }else if(root.val < key){
            root.right = deleteNode(root.right,key);
        }
        return root;
    }

    //返回该节点的前驱节点
    private TreeNode getPre(TreeNode node){
        while(node.right!=null){
            node = node.right;
        }
        return node;
    }
}
